/**
 * 链表
 */

function LinkList() {

  let Node = function(element) {
    this.element = element
    this.next = null
  }

  let length = 0
  let head = null

  // 末尾插入
  this.append = function(element) {
    let node = new Node(element),
      current = null
    if(head == null) {
      head = node
    } else {
      current = head
      // 循环找到链表末尾
      while(current.next) {
        current = current.next
      }
      current.next = node
    }
    length ++
  }

  // 某个位置插入
  this.insert = function(position, element) {
    // 越界检查
    if(position > -1 && position < length) {
      let node = new Node(element)
      if(position == 0) {
        node.next = head
        head = node
      } else {
        let index = 0,
          current = head,
          previous = null
        while(index ++ < position) {
          previous = current
          current = current.next
        }
        previous.next = node
        node.next = current
      }
      length ++
      return true
    } else {
      return false
    }
  }

  // 根据元素移除
  this.remove = function(element) {
    let current = head,
      previous = null,
      isFunded = false
    if(element == head.element) {
      head = head.next
      isFunded = true
      length --
    } else {
      while(current.next) {
        // 无法移除最后一个元素
        if(current.element == element) {
          previous.next = current.next
          isFunded = true
          break
        } else {
          previous = current
          current = current.next
        }
      }
    }
    if(isFunded) {
      length --
      return true
    } else {
      return false
    }
  }

  // 某个元素的位置
  this.indexOf = function(element) {
    let index = 0,
      current = head
    while(current) {
      if(current.element == element) {
        break
      } else {
        index ++
        current = current.next
      }
    }
    return index >= 0 ? index : -1 
  }

  // 根据位置移除
  this.removeAt = function(position) {
    if(position > -1 && position < length ) {
      let previous = null,
        current = head,
        index = 0
      if(position == 0) {
        head == current.next
      } else {
        while(index ++ < position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      length --
      return current.element
    } else {
      return null
    }
  }

  // 链表是否为空
  this.isEmpty = function() {
    return length == 0
  }

  // 链表长度
  this.size = function() {
    return length
  }

  // 打印链表
  this.print = function() {
    let current = head
    while(current.next) {
      console.log(current.element)
      current = current.next
    }
    console.log(current.element)
  }

}

let linklist = new LinkList()
linklist.append('a')
linklist.append('b')
linklist.append('c')
linklist.append('e')
linklist.append('g')
linklist.removeAt(1)
linklist.insert(2, 'f')
linklist.remove('g')
console.log(linklist.indexOf('f')+ '   f')
linklist.print()


// 双向链表

function DoubleLinkList() {
  let Node = function(element) {
    this.element = element
    this.prev = null
    this.next = null
  }

  let head = null,
    length = 0,
    last = null
  
  this.append = function(element) {
    let node = new Node(element)
    if(length == 0) {
      head = node
      last = node
    } else {
      last.next = node
      node.prev = last
      last = node
    }
    length ++
  }

  this.insert = function(element, position) {
    if(position > -1 && position < length) {
      let node = new Node(element)
      if(position == 0) {
        head.pre = node
        node.next = head
        head = node
      } else {
        let current = head,
          previous = null,
          index = 0
        while(index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = node
        node.prev = previous
        previous.next = node
        node.next = current
        current.prev = node
      }
      length ++
      return true
    } else {
      return false
    }
  }

  this.remove = function(element) {
    let current = head,
      previous = null,
      after = null,
      index = 0,
      hasFound = false
    if (head.element == element) {
      head = null
      last = null
    }
    while(index ++ < length) {
      // 可以移除最后一个元素
      if (current.element == element) {
        hasFound = true
        break
      } else {
        previous = current
        current = current.next
      }
    }
    if (hasFound) {
      previous.next = current.next
      if( current.next !== null) {
        after = current.next
        after.prev = previous
      } else {
        previous.next = null
        last = previous
      }
      length --
      return true
    } else {
      return false
    }
  }

  this.removeAt = function(position) {
    if (position < length && position > -1) {
      let index = 0,
      current = head,
      previous = null
      if(position === 0) {
        head = head.next
        head.prev = null
        length --
        return head.element
      } else {
        while(index ++ < position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
        let after = current.next
        if(after != null) {
          after.pre = previous
        }
        length --
        return current.element
      }
    } else {
      return null
    }
  }

  this.isEmpty = function() {
    return length == 0
  }

  this.size = function() {
    return length
  }

  this.head = function () {
    return head
  }

  this.print = function() {
    let current = head,
      str = ''
    while(current) {
      // console.log(current.element)
      str += current.element
      str += ","
      current = current.next
    }
    console.log(str)
  }
}

let doubleLinkList = new DoubleLinkList()
doubleLinkList.append('c')
doubleLinkList.append('d')
doubleLinkList.append('e')
doubleLinkList.insert('a', 0)
doubleLinkList.insert('r', 1)
doubleLinkList.remove('e')
console.log(doubleLinkList.removeAt(2) + '           ' + doubleLinkList.size())
doubleLinkList.print()
